package lc.q101_150;

import java.util.ArrayList;
import java.util.List;

public class Q147 {

    public ListNode insertionSortList(ListNode head) {
        ListNode tail = head;
        ListNode dumNode = new ListNode(0, head);
        while (tail.next != null) {
            ListNode next = tail.next;
            // 将next放入正确的地方
            if (tail.val <= next.val) {
                tail = next;
                continue;
            }
            ListNode now = dumNode;
            while ( now.next.val <= next.val) {
                now = now.next;
            }
            // 插入
            tail.next = next.next;
            next.next = now.next;
            now.next = next;
        }
        return dumNode.next;
    }

    public static void main(String[] args) {
        int[] arrs = new int[]{4,19,14,5,-3,1,8,5,11,15};
        ListNode head = null;
        ListNode tail = new ListNode();
        for (int arr : arrs) {
            tail.next = new ListNode(arr, tail.next);
            if (head == null) {
                head = tail.next;
            }
            tail = tail.next;
        }
        print(new Q147().insertionSortList(head));

    }

    private static void print(ListNode head) {
        ListNode nnn = head;
        List<Integer> arrs = new ArrayList<>();
        while (nnn != null) {
            arrs.add(nnn.val);
            nnn = nnn.next;
        }
        System.out.println(arrs);
    }

}
